package LeetCode_572;


import java.util.ArrayList;
import java.util.List;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/30 9:13
 */
public class Solution2 {
    // 找到所有 val 是 带查找目标的结点，填充到 List 中
    // 在 root 为根的树中进行遍历，找到 root.target == val
    // 填充到 ans 中
    private void searchAll(TreeNode root, int target, List<TreeNode> ans){
        if (root == null){
            return;
        }
        if (root.val == target){
            ans.add(root);
        }
        searchAll(root.left,target,ans);
        searchAll(root.right,target,ans);
    }
    // 判断两棵树是否相同
    private boolean isSameTree(TreeNode p, TreeNode q){
        if (p==null&&q==null){
            return true;
        }
        if (p==null||q==null){
            return false;
        }
        return p.val==q.val&& isSameTree(p.left,q.left) &&isSameTree(p.right,q.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        List<TreeNode> ans = new ArrayList<>();
        searchAll(root,subRoot.val,ans);
        for (TreeNode r : ans){
            if (isSameTree(r,subRoot)){
                return true;
            }
        }
        return false;
    }
}
